{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3618502788666131213697322783095070105526743751716087489154079457884512865582"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0x0800000000000010ffffffffffffffffb781126dcae7b2321e66a241adc64d2f - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 0x0800000000000011000000000000000000000000000000000000000000000001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = 0x0800000000000010ffffffffffffffffb781126dcae7b2321e66a241adc64d2f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "def embedding_degree(p, l):\n",
    "    pp = 1\n",
    "    for i in range(1, 10**7):\n",
    "        pp *= p\n",
    "        pp %= l\n",
    "        if pp == 1:\n",
    "            return i\n",
    "        if i % 10**6 == 0:\n",
    "            print(i, pp)\n",
    "    for n in range(100, 2, -1):\n",
    "        if pow(p, (l-1)//n, l) == 1:\n",
    "            print(\"(l-1/)\", n)\n",
    "            return (l-1)//n\n",
    "    return \"Good!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.618502788666131e+73"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(l-1)/100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1148569671075336995714074217110923280496878901117598243050720387178750002136"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(p,(l-1)//2962142, l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000000 1578306871819672483813147171655531803995321030976714780567501499271936894699\n",
      "2000000 1606712496998082715113643482710828122161979184924028104195925173172359847455\n",
      "3000000 1432592280107326262745754650815182094358089536333640591374264953315985641653\n",
      "4000000 1619747091821847920535899037397716332861452747163491677808735468629485206044\n",
      "5000000 398975072553706817943396627870660638624476176139529473762267749129551896587\n",
      "6000000 3257297284789235427779355010377513650244781788113949467967440395148285094789\n",
      "7000000 2075864992820472695981735667435876605864733562318852749859396594858790408100\n",
      "8000000 3034963322103916032347891039327850133818757400216732792182500913296186501492\n",
      "9000000 1480946314149908619442707550771106696562877433503946318227244424937788255653\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'Good!'"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "embedding_degree(p, l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# BN(2, 254)\n",
    "embedding_degree(\n",
    "    16798108731015832284940804142231733909889187121439069848933715426072753864723,\n",
    "    16798108731015832284940804142231733909759579603404752749028378864165570215949)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000000 3435807974045787183158059418534509155508744159180678228092646624578285372212\n",
      "2000000 4462034853915072829066578608116565284739508023717433171562317365936617462407\n",
      "3000000 3883824302380226806129190290611382387665993967963544705638318289833407799629\n",
      "4000000 6964862380639341224400141624862794441312849306841600305197848360981042783173\n",
      "5000000 2165175825035051265664243901541766738163081013732844725796207293622527155928\n",
      "6000000 6754163258100184884836240135329916515826078252088947735341931601219317610502\n",
      "7000000 3942668582713717401706792526557085024306293786541162995853358933716426953751\n",
      "8000000 4741195981214729907582876753056690389791056225965803559241355914424107923085\n",
      "9000000 3498425907100012849328225519764860147675260725840542411467458781460860270726\n",
      "(l-1/) 6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1206167596222043702328864427173832373476186059896651267666991823047575708498"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Curve25519\n",
    "embedding_degree(\n",
    "    57896044618658097711785492504343953926634992332820282019728792003956564819949,\n",
    "    7237005577332262213973186563042994240857116359379907606001950938285454250989\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
